同下。
长度为偶数的字符串要满足条件，那么将数组分为长度为 \(2\) 的各个小段，使各个子数组满足条件一定是最优的。
1
2
3
4
5
6
7
8
9
| class Solution {
public int minChanges(String s) {
int n = s.length(), ans = 0;
for (int i = 0; i < n; i += 2) {
ans += (s.charAt(i) ^ s.charAt(i + 1)) & 1;
}
return ans;
}
}
|
0-1 背包，转移方程为 \(dp[i][j]=\max(dp[i-1][j],dp[i-1][j-nums[i]]+1)\)，注意初始化为 \(-1\)，并在转移时判断有效性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
int n = nums.size();
int[] dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int x : nums) {
for (int j = target; j >= x; j--) {
if (dp[j - x] != -1) {
dp[j] = Math.max(dp[j], dp[j - x] + 1);
}
}
}
return dp[target];
}
}
|
动态规划 + 线段树，刚学的线段树就用上了，但是不太熟练，忘记我的线段树板子是从下标一开始操作，并且没有特判，如果操作的右端点比左端点小，那么就会导致数组越界，之后得修改一下板子。假设以 \(i\) 为右端点的所有子数组的不同计数的平方和为 \(dp[i]\)，考虑如何转移到 \(dp[i+1]\)。
如果在 \([0,i]\) 中和 \(nums[i+1]\) 相等的数为 \(nums[j]\)，则添加 \(nums[i+1]\) 会使左端点在 \([j+1,i]\) 范围内的子数组的不同计数加 \(1\)，而左端点在 \([0,j]\) 范围内子数组的不同计数不变，最后不要忘记加上左端点在 \(i+1\) 的子数组的不同计数的平方。我们可以得到如下转移方程，其中 \(x_{i,j}\) 表示子数组 \(nums[i,j]\) 的不同计数。
$$
\begin{align}
dp[i] &=x_{0,i}^{2}+x_{1,i}^{2}+\cdots+x_{i,i}^{2} \\
dp[i+1] &=x_{0,i}^{2}+\cdots+x_{j,i}^{2}+(x_{j+1,i}+1)^{2}+\cdots+(x_{i,i}+1)^{2}+x_{i+1,i+1}^{2}
\end{align}
$$
然后我们将 \(dp[i]\) 代入到 \(dp[i+1]\) 中，得到：
$$
dp[i+1]=dp[i]+2\sum_{k=j+1}^{i}x_{k,i}+(i-j)+x_{i+1,i+1}^{2}
$$
首先我们需要得到每个数，它左边第一个相同的数的位置，这可以在遍历的过程中使用哈希表得到。然后我们需要维护以当前位置为右端点，所有左端点表示的子数组的不同计数（区间修改），并且需要快速的求区间和，那么就可以使用线段树，这样我们只需要花费 \(O(\log{n})\) 的时间进行转移。转移之后，不要忘记更新左端点在 \([j+1,i+1]\) 范围内的子数组的不同计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int sumCounts(int[] nums) {
int n = nums.length;
long ans = 0L, sum = 0L;
var st = new SegmentTree(n);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i <= n; i++) {
int j = map.getOrDefault(nums[i - 1], 0);
map.put(nums[i - 1], i);
sum = (sum + 2 * st.get(j + 1, i) + i - j) % MOD;
ans = (ans + sum) % MOD;
st.add(j + 1, i, 1);
}
return (int) ans;
}
}
|